
/********************************************************************************************************
 * Option
 ********************************************************************************************************/
const Option = class {
  constructor(data){ this.data = data }
  isEmpty(){ return this.data==undefined || this.data==null || this===None }
  getOrElse(other){ return this.isEmpty() ? other : this.data }
  get(){ return this.isEmpty() ? undefined : this.data }
  map(f){ return this.isEmpty() ? other : new Option(f(this.data)) }
  flatMap(f){ return this.isEmpty() ? other : f(this.data) }
  filter(criteria){ return this.isEmpty() || !criteria(this.data) ? None : new Option(f(this.data)) }
  fold(f,init){ return this.isEmpty() ? init : f(this.data) }
  foreach(f){ if( !this.isEmpty() ) f(this.data) }
  contains(e){ return this.isEmpty() ? false : e==this.data }
  exists(criteria){ return this.isEmpty() ? false : criteria(this.data) }
  forall(criteria){ return this.isEmpty() ? true : criteria(this.data) }
}

class _None_ extends Option {
  constructor(){
    super()
  }
}

const None = new _None_()

const Some = (data) => new Option(data)

/********************************************************************************************************
 * Seq
 ********************************************************************************************************/
class Seq{

  constructor(arr){
    this.arr = arr
  }

  toArray(){ return this.arr }
  at(idx){ return this.arr.at(idx) }

  find(criteria, from=0, reverse=false){
    if( reverse ){
    }else if( from==0 || from==1-this.arr.length ){
      const res = this.arr.find( criteria )
      return res===undefined ? None : Some(res)
    }else{
      const res = this.arr.slice(from).find( criteria )
      return res===undefined ? None : Some(res)
    }
  }

}

Seq.prototype.index = function( criteria, from=0, reverse=false, thisArg=undefined ){
  if( reverse ){
    let res = -1
    if( from == -1 || from <= 1-this.length ){
      if( typeof criteria === "function" ){
	const lastEles = this.filter(criteria)
	const lastEle = lastEles[lastEles.length-1]
	res = this.lastIndexOf(lastEle)
      }else
        res = this.lastIndexOf(criteria)
    }else{
      if( typeof criteria === "function" ){
	const lastEles = this.filter(criteria)
	const lastEle = lastEles[lastEles.length-1]
	res = this.slice(0,from).lastIndexOf(lastEle)
      }else 
	res = this.slice(0,from).lastIndexOf(criteria)
    }
    return res<0 ? None : Some(res)
  }
  else if( from == 0 || from <=1-this.length ){
    let res = -1
    if( typeof criteria === "function" )
      res = this.findIndex( criteria, thisArg )
    else
      res = this.indexOf(criteria)
    return res<0 ? None : Some(res)
  }else{
    const inner_criteria = function(ele, idx, thisArg){
      return criteria( ele, idx+from, thisArg )
    }
    let ret = -1
    if( typeof criteria === "function" )
      ret = this.slice(from).findIndex( inner_criteria, thisArg )
    else
      ret = this.slice(from).indexOf(criteria)
   
    return ret<0 ? None : Some(ret+from)
  }
        
}

Seq.prototype.last = function(){ return this.arr[this.arr.length-1] }
Seq.prototype.foreach = function( action ){ return new Seq(this.arr.forEach( action )) }
Seq.prototype.map = function( action ){ return new Seq(this.arr.map( action )) }
Seq.prototype.mapFilter = function(action){ return new Seq(this.arr.map(action).filter(x=>x!=None)) }
Seq.prototype.flatMap = function( action ){ return new Seq(this.arr.flatMap( action )) }
Seq.prototype.reduce = function( action ){ return new Seq(this.arr.reduce( action )) }
Seq.prototype.fold = function( action, init ){ return new Seq(this.arr.fold( action, init )) }
Seq.prototype.flatten = function( depth = Infinity ){ return new Seq(this.arr.flat( depth )) }
Seq.prototype.filter = function( criteria ){ return new Seq(this.arr.filter( criteria )) }
Seq.prototype.distinct = function(){ new Seq(Array.from(new Set(this.arr))) }
Seq.prototype.append = function(...eles){ const res=this.arr.slice(); res.push(...eles); return new Seq(res) }
Seq.prototype.prepend = function(...eles){ const res=this.arr.slice(); res.unshift(...eles); return new Seq(res) }
Seq.prototype.insert = function(pos, ...eles){ return new Seq(this.arr.slice(0,pos).concat(eles, this.slice(pos))) }
Seq.prototype.remove = function(pos, num=1){ return new Seq(this.arr.slice(0,pos).concat(this.arr.slice(pos+num))) }
Seq.prototype.concat = function(...seqs){ return new Seq(this.arr.concat(...seqs)) }

Seq.prototype.shift = function( num=1, mode="RR" ){
  const len = this.arr.length
  const inner_num = num % len
  let res = []
  for( let res_i=0; res_i<len; res_i++ ){
    const ori_idx = (res_i + len - num) % len 
    res.push( this.arr[ori_idx] )
  }
  return new Seq(res)
}

Seq.prototype.unshift = function( num=1, mode="RR" ){
  const len = this.arr.length
  const inner_num = num % len
  let res = []
  for( let res_i=0; res_i<len; res_i++ ){
    const ori_idx = (res_i + num) % len 
    res.push( this.arr[ori_idx] )
  }
  return new Seq(res)
}

Seq.range = function(...pos){
  let st = 0
  let ed = 1
  let by = 1
  if( pos.length == 1 ){
    ed = pos[0]
  }else if( pos.length == 2 ){
    st = pos[0]
    ed = pos[1]
  }else if( pos.length == 3 ){
    st = pos[0]
    ed = pos[1]
    by = pos[2]
  }

  let res = []
  let ptr = st
  while( ptr < ed ){
    res.push( ptr )
    ptr = ptr + by
  }

  return new Seq(res)
}

Seq.repeat = function(n, ele){
  let res = []
  if( typeof ele === "function" ){
    for( let i=0; i<n; i++ ){
      res.push( ele(i) )
    }
  }else{
    for( let i=0; i<n; i++ )
      res.push(ele)
  }
  return new Seq(res)
}

class NilObj extends Seq{
  #arr;
  constructor(){super(); this.#arr = []}
  toArray(){ return [] }
  append = function(...eles){ const res=[]; res.push(...eles); return new Seq(res) }
  prepend = function(...eles){ const res=[]; res.unshift(...eles); return new Seq(res) }
  insert = function(pos, ...eles){ const res=[]; for(let i=0; i<pos; i++) res.push(undefined); res.push(...eles); return new Seq(res) }
  remove = function(pos, num=1){ return new NilObj() }
  concat = function(...seqs){ const res=[]; res.concat(...seqs); return new Seq(res) }
}

Array.prototype.toSeq = function(){ return new Seq(this) }
const Nil = new NilObj()

/********************************************************************************************************
 * Range
 ********************************************************************************************************/


const range = function(...pos){
  let st = 0
  let ed = 1
  let by = 1
  if( pos.length == 1 ){
    ed = pos[0]
  }else if( pos.length == 2 ){
    st = pos[0]
    ed = pos[1]
  }else if( pos.length == 3 ){
    st = pos[0]
    ed = pos[1]
    by = pos[2]
  }

  let res = []
  let ptr = st
  while( ptr < ed ){
    res.push( ptr )
    ptr = ptr + by
  }

  return res
}

/********************************************************************************************************
 * Tree
 ********************************************************************************************************/
const XTree = class {
  constructor( node, children=null ){
    this.node = node
    this.children = children===null ? node=>node?.children : children
  }

  static from(arr){
	  const hasRoot = arr[0].level==0
	  const brach = hasRoot ? arr.slice(1) : arr.slice()
	  let stack = hasRoot ? [arr[0]] : [{}]
	  for( let e of brach ){
	      if( e.level >= stack.length ){
		      stack[stack.length-1].children = []
      }else{
	const n = (stack.length-e.level)
	for( let i=0; i<n; i++)
	  stack.pop()
      }
	    stack[stack.length-1].children.push(e)
	    stack.push(e)
    }
	  return new XTree(hasRoot?stack[0]:stack[0].children)
  }

  /** 映射函数 */
  map( actionb, actionl=null, nchildren=null ){

    // 输入参数处理
    if( actionl == null ) actionl = actionb
    const nchild = nchildren == null ? this.children : nchildren

    // 内部迭代函数定义
    const recur = (node, idx, stack, wide) => {
      const childs  = this.children(node)  // 获取子节点
      const sstack = stack.append(node)

      if( childs ){ // 分支处理
        // 迭代处理各个子节点，然后汇总到一个数组中
    	  const ret = childs.map( (c,i)=>recur(c, idx.append(i), sstack, wide.append(childs.length)) )
        return actionb( node, idx, ret, sstack, wide )   // Callback用户定义的处理函数
      }else // 叶子处理
        return actionl( node, idx, [], sstack, wide )
    }

    return new XTree( recur( this.node, [], [], [] ), nchild )
  }

  level(){
    const iter = function(nodes,lvl){
      return nodes
	      .map(node=>node.children===undefined ? lvl : iter(node.children, lvl+1) )
	      .reduce( (a,b)=>Math.max(a,b), 0)
    }

    if( this.hasRoot ) return iter( [this.node], 1 )
    else return iter( this.node, 1 )
  }

}

XTree.prototype.find = function(criteria){ (new MTree([this.node], this.children))._findInner_(criteria, false) }

const xtree = function(node, children=null){return new XTree(node, children)}


const MTree = class {
  
  constructor( node, children ){

    // node类型检查
    console.assert( Array.isArray(node), `MTree only acept Array type parameter for 'node', but node=${node} ` )
    this.node = node

    // children类型检查
    if( children === null ){
      console.assert( node.children !== undefined, `MTree parameter 'node' should has 'children' attribute when parameter 'children' is null` )
      children = node.children 
    }
    console.assert( typeof children === "function", `MTree only acept Function type parameter for 'children', but children=${children}` )
    console.assert( children.length===1, `MTree parameter 'children' only acept 1 argument. ` )
    this.children = children
  }

  static from(arr){
	  const hasRoot = arr[0].level==0
	  const brach = hasRoot ? arr.slice(1) : arr.slice()
	  let stack = hasRoot ? [arr[0]] : [{}]
	  for( let e of brach ){
	      if( e.level >= stack.length ){
		      stack[stack.length-1].children = []
      }else{
	const n = (stack.length-e.level)
	for( let i=0; i<n; i++)
	  stack.pop()
      }
	    stack[stack.length-1].children.push(e)
	    stack.push(e)
    }
	  return new XTree(hasRoot?stack[0]:stack[0].children)
  }

  /** 映射函数 */
  map( actionb, actionl=null, nchildren=null ){

    // 输入参数检查和处理
    if( actionl == null ) actionl = actionb
    console.assert( typeof actionb==="function", `MTree.map parameter 'actionb' should be function` )
    console.assert( actionb.length===5, `MTree.map parameter 'actionb' should have 5 arguments.` )
    console.assert( typeof actionl==="function", `MTree.map parameter 'actionl' should be function` )
    console.assert( actionl.length===5, `MTree.map parameter 'actionl' should have 5 arguments.` )

    const nchild = nchildren == null ? this.children : nchildren

    // 内部迭代函数定义
    const recur = (node, idx, stack, wide) => {
      const childs  = this.children(node)  // 获取子节点
      stack.push(node)

      if( childs && childs.length>0 ){ // 分支处理
        
        const wwide = wide.slice()
        wwide.push(childs.length)

        // 迭代处理各个子节点，然后汇总到一个数组中
    	  const ret = childs.map( (c,i)=>{
          const iidx = idx.slice()
          iidx.push(i)
          return recur(c, iidx, stack, wwide)
        } )
        return actionb( node, idx, ret, stack, wide )   // Callback用户定义的处理函数
      }else // 叶子处理
        return actionl( node, idx, [], stack, wide )
    }

    const res = this.node.map( n => recur( n, [], [], [] ) )

    return new MTree( res, nchild )
  }

  _findInner_(criteria, isMTree=true){

    // 内部迭代函数定义。注意：idx/stack/wide都为Seq类型，返回值也是Seq类型
    const recur = (node, idx, stack, wide) => {
      const childs  = this.children(node)  // 获取子节点
      const sstack = stack.append(node)

      if( childs && childs.length>0 ){ // 分支处理
        // 迭代处理各个子节点，然后汇总到一个数组中
    	  const ret = childs.map( (c,i)=>recur(c, idx.append(i), sstack, wide.append(childs.length)) )
        const res = criteria( node, idx.toArray(), ret, sstack.toArray(), wide.toArray() )   // Callback用户定义的处理函数
        if( res ) return Some(sstack)   // 优先返回父节点
        for( let s of ret ) if( !s.isEmpty() ) return s
        return None
      }else{ // 叶子处理
        const res = criteria( node, idx.toArray(), [], sstack.toArray(), wide.toArray() )
        return res ? Some(sstack) : None
      }
    }

    for( let i=0; i<this.node.length; i++ ){
      const idx = isMTree ? [i] : []
      const wide = isMTree ? [this.node.length] : []
      const res = recur( this.node[i], idx.toSeq(), [this.node[i]].toSeq(), wide.toSeq() )
      if( !res.isEmpty() ) return res
    }

    return None
  }

  level(){
    const iter = function(nodes,lvl){
      return nodes
	      .map(node=>node.children===undefined ? lvl : iter(node.children, lvl+1) )
	      .reduce( (a,b)=>Math.max(a,b), 0)
    }

    if( this.hasRoot ) return iter( [this.node], 1 )
    else return iter( this.node, 1 )
  }

  
}

MTree.prototype.find = function( criteria ){ return this._findInner_(criteria) }


const mtree = function(node, children=null){return new MTree(node, children)}


//============================================================================================
// Dict
//============================================================================================
const Dict = class {
  constructor(obj){ this.data = obj }
}

Dict.prototype.concat = function(...dicts){
  let res = {}
  for( let key in this.data )
    res[key] = this.data[key]
  for( let dict of dicts )
    for( let key in dict )
      res[key] = dict[key]
  return new Dict(res)
}

Dict.prototype.append = function(){
  let res = {}
  for( let key in this.data )
    res[key] = this.data[key]
  const valid_size = arguments.length%2 ? arguments.length-1 : arguments.length
  for( let i=0; i<valid_size/2; i++ ){
    key = arguments[i*2]
    value = arguments[i*2+1]
    res[key] = value
  }
  return new Dict(res)
}

Dict.prototype.contains = function(...keys){
  for( let key of keys ){
    if( this.data.key !== undefined )
      return true
  }
  return false
}



export {
  XTree,
  xtree,
  MTree,
  mtree,
  range,
  Dict,
  
  Option,
  None,
  Some,
  
  Seq,
  Nil,
};
